Mi manual de algoritmos/source_highlight/src/grafos/prim.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <map>
   4 #include <queue>
   5 #include <set>
   6
   7 using namespace std;
   8
   9 typedef pair<double, double> point;
  10 //Gives a vector of adjacent nodes to a point
  11 typedef map< point, vector<point> > graph;
  12 //Edge of length "first" that arrives to point "second"
  13 typedef pair<double, point> edge;
  14
  15 double euclidean(const point &a, const point &b){
  16   return hypot(a.first-b.first, a.second-b.second);
  17 }
  18
  19
  20 int main(){
  21   int casos;
  22   cin >> casos;
  23   while (casos--){
  24     graph g;
  25     int n;
  26     cin >> n;
  27     while (n--){
  28       double x,y;
  29       cin >> x >> y;
  30       point p(x,y);
  31       if (g.count(p) == 0){ //Si no está todavía
  32         vector<point> v;
  33         g[p] = v;
  34         for (graph::iterator i = g.begin(); i != g.end(); ++i){
  35           if ((*i).first != p){
  36             (*i).second.push_back(p);
  37             g[p].push_back((*i).first);
  38           }
  39         }
  40       }
  41     }
  42
  43     set<point> visited;
  44     priority_queue<edge, vector<edge>, greater<edge> > q;
  45     //Each edge in q has got a length "first" and a point "second".
  46     //It means I can reach point "second" which is "first" meters away.
  47     //q has the closest reachable node on top (I may have already visited it!)
  48     q.push(edge(0.0, (*g.begin()).first));
  49     double totalDistance = 0.0;
  50     while (!q.empty()){
  51       edge nearest = q.top();
  52       q.pop();
  53       point actualNode = nearest.second;
  54       if (visited.count(actualNode) == 1) continue; //Ya habia visitado este
  55       totalDistance += nearest.first;
  56       visited.insert(actualNode);
  57       vector<point> neighbors = g[actualNode];
  58       for (int i=0; i<neighbors.size(); ++i){
  59         point t = neighbors[i];
  60         double dist = euclidean(actualNode, t);
  61         q.push(edge(dist, t));
  62       }
  63     }
  64     printf("%.2f\n", totalDistance);
  65     if (casos > 0) cout << endl; //Endl between cases
  66   }
  67 }